The invention generally relates to performing comparison operations between or among digital data and generating data entries to be used for such operations. In particular, it is directed to computer processes, network communication systems, pattern recognition systems, or any system in which data entries are generated to be used for comparison operation with incoming data or with each other in order to make content-based decisions.
There are many areas of digital data processing in which two or more digital data are compared with each other to derive relationships between or among them. Some examples are to classify data according to criteria, to parse packet data to identify their protocol type, and to perform database searches to name a few.
Data network communication systems are an area where these operations can be described in more detail. The increasing network traffic and the diversity of services provided by today""s networks, require some distinction to be made for some type of services and packets. For example, network requirements for voice or video packet transmission are not the same as for File Transfer Protocol (ftp) application packet, or network management packets. The recent introduction of Quality of Service (QoS) and Class of Service (CoS) concepts in networks, are making packet classification more critical than it was in the past. In order to be able to prioritize and provide a required quality of service for a given packet, the packet has to be recognized as requiring certain QoS or CoS. Packet classification is an important step in providing QoS and CoS based services. The packets are classified according to the values contained within their headers, which indicate the type of their flow. The more precise the packet analysis, the better the classification. Many encapsulated headers may be looked-up to make a decision about the packet class.
In general, packet classification involves first identifying different incoming network packet headers and more specifically fields contained within these headers. The second step involves comparing the different header fields to fixed values or comparing the fields between themselves. In differentiated service systems, i.e., system implementing CoS and QoS whereby the type of service can be differentiated in order to increase the processing rates, the time allocated for packet header processing has to be minimized.
Many conventional packet classification techniques involving software are currently used or under development, which perform classifications using binary trees or accelerated search algorithms. These conventional techniques use a xe2x80x9cperfect matchxe2x80x9d approach (exact equality comparison) wherein the search data are compared with a fixed value and either an exact match is found or a mismatch or miss is detected.
Recent advances in content addressable memories (CAMs) have provided an attractive hardware alternative for implementing such packet classification tasks to the conventional software techniques. CAMs perform parallel searches of specified data vs. stored data to output a match or a mismatch result designated by an address (in the case of a match). CAM cell structure can be either binary or ternary. Binary CAM cells can store either a logic xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d, while ternary CAM cells can store a logic xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d, or a xe2x80x9cdon""t carexe2x80x9d state. A xe2x80x9cdon""t carexe2x80x9d state or value, also denoted by xe2x80x9cxxe2x80x9d means that the value can be either a xe2x80x9c0xe2x80x9d or a xe2x80x9c1xe2x80x9d. Typically, these three states are encoded using two bits. For example, the value xe2x80x9c0xe2x80x9d can be stored as xe2x80x9c00xe2x80x9d, the value xe2x80x9c1xe2x80x9d as xe2x80x9c01xe2x80x9d and the xe2x80x9cdon""t carexe2x80x9d value as xe2x80x9c10xe2x80x9d with the fourth case xe2x80x9c11xe2x80x9d being an unused state.
Generally, both binary and ternary CAMs have mask registers that can be used during search operations to ignore or xe2x80x9cmaskxe2x80x9d some of the bits for comparisons. In this description, a bit in the mask bit register that is set to xe2x80x9c0xe2x80x9d means that the corresponding bit in the input data (or the key) is to be compared to the corresponding bit in the CAM entries. A mask bit that is set to xe2x80x9c1xe2x80x9d in the mask bit register, means that the result of the comparison of the corresponding bit in the input data (key) with the corresponding bit in the CAM entries does not matter. In the case of ternary CAMs, bits that are set to xe2x80x9cdon""t carexe2x80x9d value in CAM entries, will always match the corresponding bits in the input data independently of the mask value for these bits. In the remainder of the description, concepts will be equally applicable to both binary and ternary CAMs unless otherwise specified.
The introduction of masking in binary CAMs and xe2x80x9cdon""t carexe2x80x9d values in ternary CAMs allow comparisons other than the xe2x80x9cequalityxe2x80x9d. Comparisons such as xe2x80x9cgreater thanxe2x80x9d, xe2x80x9cless thanxe2x80x9d, and xe2x80x9cinequalityxe2x80x9d to a fixed value, as well as comparing two fields of incoming data can be implemented. Mask register and xe2x80x9cdon""t carexe2x80x9d features are used in several prior art implementations. For example, U.S. Pat. No. 5,920,886 Jul. 6, 1999 Feldmeier uses these features to implement hierarchical address filtering and translation. In this prior art reference, masks and the xe2x80x9cdon""t carexe2x80x9d values are used to perform comparisons extending the xe2x80x9cequalityxe2x80x9d relationship but it uses a priority fields to represent hierarchical levels.
U.S. Pat. No. 4,996,666 Feb. 26, 1991 Duluk, Jr. describes a CAM system for performing fully parallel magnitude comparisons between xe2x80x98stored and input data based on a specific hardware implementation. The proposed CAM implementation is also capable of performing multiple comparisons on multiple fields of the CAM entries in one clock cycle. Comparisons such as xe2x80x9cequalityxe2x80x9d, xe2x80x9cless thanxe2x80x9d, xe2x80x9cless than or equal toxe2x80x9d, xe2x80x9cgreater thanxe2x80x9d, xe2x80x9cgreater than or equal toxe2x80x9d, xe2x80x9cinequalityxe2x80x9d, and xe2x80x9cdon""t carexe2x80x9d (field ignored) can be performed. The results of the different comparisons are stored in flag bits associated with each CAM entry. The more flag bits the CAMxe2x80x2 has, the larger is the number of comparisons and fields of the CAM. However, the proposed solution is a custom hardware solution requiring significant area. Furthermore, the patent fails to describe techniques of flexibly generating the CAM entries.
U.S. Pat. No. 3,320,592 May 16, 1967 Rogers et al. also describes a hardware implementation of a CAM based comparisons other than equality in one cycle. This implementation supports binary data storage only and is hardware-specific.
U.S. Pat. No. 3,389,377 Jun. 18, 1968 Cole describes a CAM capable of performing xe2x80x9cgreater thanxe2x80x9d and xe2x80x9cless thanxe2x80x9d comparisons using a bit-sequential algorithm where bits of a field to be compared are scanned from the most significant bit to the least significant bit. This reference describes only binary CAMs with no masking capabilities with hardware-specific modifications to conventional CAMs. A non-flexible sensing scheme is also described which further constrains the flexibility of CAMs.
In summary, all these prior art solutions describe either software implementations or customized hardware solutions for performing comparison operations. In addition, none of the above prior art references describes a flexible and efficient way of generating searchable entries intended to minimize the number of entries required for performing the search and compare functions.
The invention therefore addresses techniques of generating searchable data entries in a storage medium. The invention also resides in techniques of performing comparison operation between an unknown value, against a fixed value or between fields within a digital stream. The present invention does not require any specific hardware implementation except the ability to use masks during a search operation, or alternately the ability to have xe2x80x9cdon""t carexe2x80x9d states stored. The storage medium can be of the type of CAM used; i.e. binary or ternary SRAM or DRAM-based CAMs can be used to implement the present invention.
Briefly stated, the invention is directed to a method of generating data entries to be written in a storage medium which supports comparison-type operations. The method includes the steps of identifying a reference value having a predetermined number P of binary bits and identifying a comparison-type indicator indicating the type of comparison operation which includes xe2x80x9cgreater thanxe2x80x9d, xe2x80x9cless thanxe2x80x9d xe2x80x9cequal toxe2x80x9d, xe2x80x9cgreater than or equal toxe2x80x9d and xe2x80x9cless than or equal toxe2x80x9d. The method includes further steps of determining the bit pattern of the reference value and generating a set of data entries to be written in response to the comparison-type indicator and the bit pattern. In further aspect of the invention, the storage medium is binary CAM or ternary CAM.
In accordance with another aspect, the invention is directed a method of performing a comparison-type operation against the reference value by using a CAM. The method comprises steps of searching for the reference value in a storage medium which contains the data entries generated responsive to the bit pattern and the comparison-type indicator to produce a result which includes no match, a match and a multiple matched, and determining the comparison relationship against the reference value in response to the result.
In accordance with a further aspect, the invention is directed to a method of generating data entries to be written in a storage medium which supports a comparison-type operation between two fields within a digital datum, one field being P binary bits long, the other being S binary bit long and P and S being positive integers. The method comprises steps of identifying a comparison-type indicator indicating the type of comparison operation which includes one field being xe2x80x9cgreater thanxe2x80x9d, xe2x80x9cless thanxe2x80x9d xe2x80x9cequal toxe2x80x9d, xe2x80x9cgreater than or equal toxe2x80x9d and xe2x80x9cless than or equal toxe2x80x9d the other field and generating a set of data entries of at least P+S bits long to be written in response to the comparison-type indicator, each of the data entries comprising two subentries of at least P and S bit long respectively.
In yet a further aspect, the two fields between which a comparison-type operation is performed can be from the same digital data stream. In one embodiment, the digital stream is a header of communications packet and the method of the invention can be applied to parse (classify) the packet by performing comparison operations to the fields within the header.
In further aspect, the invention is directed to electronic systems for performing variety, of comparison-type operations.